1. Field of the Invention
The present invention relates to a fault propagation path estimating method and a fault propagation path estimating apparatus for accurately estimating a fault point in a combinational logic circuit, and a recording medium therefor.
2. Description of the Related Art
A fault propagation path estimating apparatus, which extracts a path through which a faulty state may propagate in a combinational logic circuit, can be used as part of a fault diagnostic system for a sequential circuit as described in JP-A-08-146093 or JP-A-10-062494. A fault may exist inside a combinational logic circuit or a faulty state may be included in an input signal pattern.
Conventional methods of estimating a fault propagation path include an inverse logical expansion method which applies a back track method disclosed in JP-A-10-154171. This is a method of extracting a fault propagation path by comparing the estimated logical state of an input signal derived with the inverse logical expansion method and the logical state inside a combinational logic circuit derived in the process with a logical state (hereinafter referred to as xe2x80x9cexpected valuexe2x80x9d) of each node derived from a previous logical simulation of a normal circuit.
In such a method, however, when the logical states of respective signal lines (lines for connecting gates which serve as components of the circuit) are estimated, the existence of multipliers or the like in the combinational logic circuit causes a significant number of decisions for the logical states of the signal lines, leading to a long time expected for calculation. To avoid this, a method is contemplated which provides faster estimation of a fault propagation path by limiting decision processing only to the signal lines relating to the fault propagation path. A conventional fault propagation path estimating apparatus for performing such processing is hereinafter described with reference to FIG. 1 and FIG. 2.
FIG. 1 is a block diagram showing a configuration of the conventional fault propagation path estimating apparatus, and FIG. 2 is a block diagram showing a configuration of an implication operation unit. It should be noted that the fault propagation path estimating apparatus shown in FIG. 1 logically estimates a fault propagation path by repeating decisions and implication operations from a signal line in a known logical state in a combinational logic circuit, and does not estimate a fault propagation path by actually inputting a signal to the combinational logic circuit.
In FIG. 1, the conventional fault propagation path estimating apparatus comprises input device 11 such as a keyboard, data processing unit 12 for estimating a fault propagation path in a combinational logic circuit, storage device 14 including a hard disk or memory for storing information, and output device 15 such as a display or printer.
Storage device 14 comprises logic circuit configuration storing section 141 for storing the configuration of the combinational logic circuit for which a fault propagation path is to be estimated, such as types of gates which serve as components of the circuit, connections between the gates, connections between the gates and signal lines, connections between the signal lines and the like; decision state storing section 143 for storing decision levels at the estimation of the logical states of the respective signal lines with implication operations, later described; and logical state storing section 144 for storing the logical states of the respective signal lines during estimation and the expected values of the respective signal lines, respectively. The decision level represents the accumulated number of decisions (for the entire circuit) at the point of the decision of a logical state for a signal line.
Data processing unit 12 comprises initial setting section 121 for setting the logical states of input/output terminals in the combinational logic circuit in specified states at the estimation of a fault propagation path; implication operation section 123 for estimating a logical state for each signal line in the combinational logic circuit; logical contradiction determining section 124 for determining whether or not a contradiction occurs in the logical states of the signal lines estimated by implication operation section 123; processing end determining section 125 for determining whether or not the logical states of all the signal lines have been estimated in the combinational logic circuit; X (Don""t Care) state setting section 122 for setting the initial logical state of a signal line in an unestimated logical state in an X (Don""t Care) state and recording this in logical state storing section 144; back track section 126 for erasing the decided logical state of a signal line for which the logical state has already been estimated and returning the logical states of the respective signal lines to the logical states before the decisions; logical value comparing section 130 for comparing the logical states of the respective signal lines estimated in the implication operations with the expected values of the respective signal lines to extract a fault propagation path; fault output terminal connected and related line extracting section 131 for extracting any fault propagation path of the fault propagation paths extracted by logical value comparing section 130 that has a fault thereon directly affecting an output terminal and outputting associated data to output device 15; U (Unknown) state search section 127 for checking the logical states of the inputs and outputs of the respective gates which serve as components of the combinational logic circuit to detect any signal line in a logical state Unknown (undefined); fault propagation path affecting line search section 128 for detecting any signal line relating to any fault propagation path from the signal lines in the Unknown state; and logical value decision section 129 for deciding the logical state of a signal line in the logical state Unknown connected through a gate to the signal line on the fault propagation path detected by fault propagation path affecting line search section 128. The signal line on the fault propagation path refers to a signal line in which the estimated logical state is different from the expected value.
As shown in FIG. 2, implication operation section 123 comprises implication operation-capable gate search subsection 238 for detecting any gate for which the implication operation can be performed; basic implication operation subsection 241 for estimating the logical states of respective input/output signal lines of a gate connected to the input/output terminal set by initial setting section 121, of a gate connected to the signal line decided by logical value decision section 129, and of the gate detected by implication operation-capable gate search subsection 238; logical contradiction detecting subsection 240 for detecting whether or not the logical state newly estimated by basic implication operation subsection 241 contradicts previously estimated the logical state; and implication operation end determining subsection 239 for determining that all the implication operations are completed when no implication operation-capable gate is detected.
The logical states of the respective signal lines are estimated by basic implication operation subsection 241 as xe2x80x9c0,xe2x80x9d xe2x80x9c1,xe2x80x9d xe2x80x9cXxe2x80x9d or xe2x80x9cU.xe2x80x9d The newly estimated logical state of the signal line is recorded in logical state storing section 144, and the decision level at that point is recorded in decision state storing section 143. The implication operation-capable gate refers to a gate in which the logical state of an input or output signal line in an undecided logical state may be estimated from the decided logical state (xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d) of an input or output signal line with the implication operation based on the function of the gate.
Next, the operation of the conventional fault propagation path estimating apparatus is described using FIG. 3 to FIG. 5 with reference to FIG. 1 and FIG. 2.
FIG. 3 is a flow chart showing a procedure of processing in the data processing unit shown in FIG. 1, and FIG. 4 is a flow chart showing a procedure of processing in the implication operation section shown in FIG. 2. FIG. 5 is a diagram showing an example of implication operation results of the conventional fault propagation path estimating apparatus in the form of a circuit diagram showing estimation results of logical states of inputs and an output in a two-input NAND gate.
The logical states of the respective signal lines estimated by the conventional fault propagation path estimating apparatus shown in FIG. 1 are xe2x80x9c0,xe2x80x9d xe2x80x9c1,xe2x80x9d xe2x80x9cU (Unknown),xe2x80x9d and xe2x80x9cX (Don""t Care).xe2x80x9d xe2x80x9cU (Unknown)xe2x80x9d represents an undefined state in which the logical state of a signal line cannot be determined either xe2x80x9c0xe2x80x9d or xe2x80x9c1,xe2x80x9d while xe2x80x9cx (Don""t Care)xe2x80x9d represents a case where either logical state xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d of a signal line cause no contradiction in the logical state of the entire combinational logic circuit, in other words, either logical state is permitted.
The conventional fault propagation path estimating apparatus shown in FIG. 1 performs, using a signal line in a known logical state as a base point, an implication operation for each gate connected to the signal line to estimate a logical state of a signal line located across the gate. Similar processing is then repeated based on the estimated logical state to estimate the respective logical states of the signal lines in the combinational logic circuit. For a signal line in the logical state xe2x80x9cU (Unknown)xe2x80x9d connected through a gate to a signal line on a fault propagation path, its logical state is decided as xe2x80x9c0xe2x80x9d and xe2x80x9c1,xe2x80x9d and based on the decided logical state, an implication operation similar to the aforementioned operation is repeated to extract a fault propagation path. In the case of a fault present in the combinational logic circuit, since the implication operations repeated with decisions result in a logical contradiction generated in the fault propagation path, the fault propagation path estimating apparatus shown in FIG. 1 terminates the implication processing at the point of the detection of such a logical contradiction.
In FIG. 3, data processing unit 12 first uses initial setting section 12 to set the logical states of the input/output terminals of the combinational logic circuit for which a fault path is to be estimated in specified states through input device 11 (step C1) to initialize a decision level (dlevel=0) (step C2). Data processing unit 12 sets the logical states of signal lines in undecided logical states to xe2x80x9cXxe2x80x9d or the initial state of the implication operation, and records the processing result in logical state storing section 144 (step C3).
Next, data processing unit 12 performs the implication operation using implication operation section 123 (step C4). The implication operation refers to processing for estimating an unestimated logical state of an input or output signal line from the estimated logical state of an input or output signal line of a gate. The procedure of the implication operation is described using FIG. 4.
In FIG. 4, implication operation section 123 first searches an implication operation-capable gate using implication operation-capable gate search subsection 238 (step D1).
Subsequently, implication operation end determining subsection 239 is used to determine whether or not all the implication operations are completed (step D2). At step D2, implication operation end determining subsection 239 determines that all the implication operations are not completed if any implication operation-capable gate is detected, or determines that all the implication operations are completed if no implication operation-capable gate is detected.
If all the implication operations are determined as complete at step D2, the processing is moved to step C5 shown in FIG. 3. Alternatively, if all the implication operations are determined as incomplete, implication operation section 123 performs the implication operation for the gate detected at step D1 using basic implication operation subsection 241 to estimate the logical states of the input/output signal lines.
Basic implication operation subsection 241 estimates the logical state of the input/output signal lines for which the initial setting has been performed at step C1 in FIG. 3, and the logical state of each input/output signal line of a gate connected to the signal line for which the logical state has been decided by logical value decision section 129 and of the implication operation-capable gate detected by implication operation-capable gate search subsection 238. The estimated logical states are recorded in logical state storing section 144, while the decision level at that point is recorded in decision state storing section 143.
As an example of the implication operation in the conventional fault propagation path estimating apparatus, FIG. 5 shows results of implication operations for a two-input NAND gate. FIG. 5(a) shows estimation results of the logical state of an output signal line when the logical states of input signal lines of the two-input NAND gate are determined, while FIG. 5(b) shows estimation results of the logical states of the input signal lines when the logical state of the output signal line of the two-input NAND gate is determined.
As shown in FIG. 5(a), in the case of the NAND gate, if the logical state xe2x80x9c0xe2x80x9d is present on either of the input signal lines, the output signal line is estimated as the logical state xe2x80x9c1.xe2x80x9d If both logical states of the input signal lines are xe2x80x9c1,xe2x80x9d the output-signal line is estimated as the logical state xe2x80x9c0.xe2x80x9d
As shown in FIG. 5b, if the state of the output line of the two-input NAND gate is xe2x80x9c0xe2x80x9d, both logical states of the input signal lines are estimated as xe2x80x9c1.xe2x80x9d If the state of the output line of the two-input NAND gate is xe2x80x9c1xe2x80x9d and the logical state of one of the input signal lines is xe2x80x9c1,xe2x80x9d the logical state of the other input signal line is estimated as xe2x80x9c0.xe2x80x9d
Upon completion of the implication operation at step D3 shown in FIG. 4, implication operation section 123 detects whether or not any contradiction occurs between the newly estimated logical states and the previously estimated logical state using logical contradiction detecting subsection 240 (step D4). If no logical contradiction is detected, the processing returns to step D1 and the processing from step D1 to D4 is repeated. Alternatively, if any logical contradiction is detected at step D4, the implication operation is terminated to move to the processing at step C5 shown in FIG. 3.
Upon completion of the implication operation at step C4, data processing unit 12 determines whether or not any logical contradiction occurs in the respective signal lines from the implication operation using logical contradiction determining section 124 (step C5). If any logical contradiction is present, the processing moves to step C12, later described. Alternatively, if no logical contradiction is present, processing end determining section 125 is used to determine whether or not the logical states of all the signal lines have been estimated (step C6).
If data processing unit 12 determines that the logical states of all the signal lines have not been estimated, it checks the input/output logical states of the respective gates in the combinational logic circuit using U (Unknown) state search section 127 to search any signal line in an undefined logical state or Unknown (step C7), and detects any signal line relating to a fault propagation path from the signal lines in the Unknown state using fault propagation path affecting line search section 128 (step C8).
Next, logical value decision section 129 is used to decide the logical state as xe2x80x9c0xe2x80x9d of the signal line detected by fault propagation path affecting line search section 128, and increments the decision level by one (dlevel +1) (step C9). Then, the processing returns to step C4 to perform the implication operation for that signal line using implication operation section 123.
On the other hand, if data processing unit 12 determines that the logical states of all the signal lines have been estimated at step C6, the logical states of the signal lines have been defined as xe2x80x9c0,xe2x80x9d xe2x80x9c1xe2x80x9d or xe2x80x9cX.xe2x80x9d Thus, logical value comparing section 130 is used to extract any signal line in a logical state different from that of the expected value, i.e. a fault propagation path (step C10).
In addition, fault output terminal connected and related line extracting section 131 is used to extract any fault propagation path which affects the output terminal (fault output terminal) of the combinational logic circuit, and the fault propagation path is outputted using output device 15 (step C11).
Next, data processing unit 12 determines, using processing end determining section 125, whether or not the signal lines after decisions (hereinafter referred to as xe2x80x9cdecided linexe2x80x9d) have been subjected to decisions for both xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d (step C12), and if all the decision processing is completed, terminates the fault propagation path extracting processing.
If all the decision processing is not completed, back track section 126 is used to extract one of the decided lines which have not been decided as xe2x80x9c1xe2x80x9d that has a greater decision level, and the logical state of the signal line estimated with decision processing corresponding to a greater decision level than that of the extracted decided line is initialized to xe2x80x9cUxe2x80x9d to return the logical states of the respective signal lines to the logical states before the decision (step C13).
Subsequently, the logical state of the decided line extracted at step C13 is decided as xe2x80x9c1xe2x80x9d (step C14), and the processing returns to step C4 to again perform the implication operation.
Next, specific description is made for the estimation processing for a fault propagation path with the conventional fault propagation path extracting apparatus using combinational logic circuits shown in FIG. 6 and FIG. 7 as examples.
FIG. 6 and FIG. 7 are circuit diagrams showing examples of a combinational logic circuit for which a fault propagation path is estimated. First, description is made for a case where a fault propagation path in the combinational logic circuit shown in FIG. 6 is extracted with the conventional fault propagation path extracting apparatus shown in FIG. 1. It is assumed that the combinational logic circuit shown in FIG. 6 has a fault occurring at the output signal line of gate G1 and that the logical states of input terminals L1, L2 and output terminals L7, L8 and L9 are given at the initial setting. Each symbol in brackets [ ] for each signal line represents a result of a comparison with the expected value, either in a normal state (T: True) or a fault state (F: False). In the case of the combinational logic circuit shown in FIG. 6, the fault occurring at the output of gate G1 propagates through signal lines L3, L5 and L6 to signal lines L7 and L9 connected to output terminals. It is assumed herein that only the logical states of the input terminals and output terminals can be observed, and the logical states of the signal lines other than those are not known.
In FIG. 6, when the logical states of the input terminals and output terminals are specified as L1=[T], L2=[T], L7=[F], L8=[T], and L9=[F] through input device 11, data processing unit 12 sets the logical states of the input terminals and output terminals in specified states using initial setting section 121, and sets the logical states of the signal lines other than the input/output terminals to xe2x80x9cXxe2x80x9d using X (Don""t Care) state setting section 122 (steps C1 to C3).
Next, data processing unit 12 detects any implication operation-capable gate from within the ombinational logic circuit using implication operation-capable gate search subsection 238 in implication operation section 123 (step D1). In this example, gates G5, G6, and G7 are detected, and implication operation processing is continued in response to the determination that the implication operation is not completed (step D2).
Data processing unit 12 then performs implication operations using basic implication operation subsection 241 in implication operation section 123, and estimates L5=[F] with the implication operation for gate G5, L6=[F] with the implication operation for gate G6, and L4=[T] with the implication operation for gate G7 (step D3).
Next, data processing unit 12 determines whether any logical contradiction exists in the logical states estimated by basic implication operation subsection 241 using logical contradiction detecting subsection 240 in implication operation section 230 (step D4). Specifically, the logical states of the input/output signal lines of the respective gates are estimated as xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d using a true table, and the result is compared with the expected value to determine [T] or [F].
Since no logical contradiction occurs in this example, implication operation section 123 returns to step D1 and again searches any implication operation-capable gate and detects gates G2, G3, and G4 (step D1).
Next, implication operation section 123 in data processing unit 12 performs implication operations for the respective gates detected at step D1 using basic implication operation subsection 241, and estimates L2=[T] with the implication operation for gate G2, L3=[F] with the implication operation for gate G3, and L3=[F] with the implication operation for gate G4 (step D3).
Then, implication operation section 123 uses logical contradiction detecting subsection 240 to determine whether any logical contradiction occurs in the logical states estimated by basic implication operation subsection 241. Again, no logical contradiction occurs to the previously estimated logical states (step D4). Therefore, implication operation section 123 returns to step D1 and again searches any implication operation-capable gate and detects gate G1.
Next, data processing unit 12 estimates L1=[F] with the implication operation for gate G1 (step D3). However, since input terminal L1 has been specified as L1=[T] at the initial setting, a logical contradiction is detected to terminate the implication operation (step D4).
With the aforementioned processing, the logical states of all the signal lines are estimated respectively, and signal lines L3, L5, L6, L7, and L9 are obtained as a fault propagation path.
Next, description is made for a case where a fault propagation path is estimated with the conventional fault propagation path estimating apparatus in a combinational logic circuit with a loop present as shown in FIG. 7.
When a fault propagation path in the combinational logic circuit shown in FIG. 7 is extracted, the procedure until the initial setting of the logical states of the input/output terminals to L1=[T], L2=[T], L7=[F], L8=[T], and L9=[F] are similar to that in the combinational logic circuit shown in FIG. 6 (steps C1 to C3).
Next, data processing unit 12 searches any implication operation-capable gate using implication operation-capable gate search subsection 238 in implication operation section 123 (step D1). Gates G1, G5, G6, and G7 are detected in this example, and implication operation processing is continued in response to the determination that the implication operation is not completed (step D2).
Subsequently, data processing unit 12 performs implication operations for the respective gates detected at step D1 using basic implication operation subsection 241 in implication operation section 123, and estimates L5=[F] with the implication operation for gate G5, L6=[F] with the implication operation for gate G6, and L4=[T] with the implication operation for gate G7. Since output terminal L8 is connected to the input of gate G1 in the combinational logic circuit shown in FIG. 7, L3=[T] is estimated with the implication operation for gate G1 (step D3).
Next, data processing unit 12 determines whether any logical contradiction exists in the logical states estimated by basic implication operation subsection 241 using logical contradiction detecting subsection 240 in implication operation section 123 (step D4). Since no logical contradiction occurs in this example, the processing returns to step D1 and any implication operation-capable gate is again searched and gates G2, G3, and G4 are detected (step D1).
Subsequently, data processing unit 12 performs implication operations for the respective gates detected at step D1 using basic implication operation subsection 241 in implication operation section 123, and estimates L2=[T] with the implication operation for gate G2, L3=[F] with the implication operation for gate G3, and L3=[F] with the implication operation for gate G4. At this point, since the logical state of signal line L3 has been estimated as L3=[T], a logical contradiction is detected at step D4 to terminate the implication operation processing.
With the aforementioned processing, the logical states of all the signal lines are estimated, and signal lines L5, L6, L7, and L9 can be obtained as a fault propagation path. However, since signal line L3 which is a fault point is estimated as [T], it is not estimated as a fault propagation path and is not included in fault candidates.
As described above, the conventional fault propagation path estimating apparatus has a problem that, when a loop exists within the combinational logic circuit for which a fault propagation path is estimated, a signal line on which a fault occurs may not be extracted as part of the fault propagation path, thereby exhibiting low accuracy of fault point estimation.
Additionally, since the implication operation is terminated at the point of the detection of a logical contradiction, the conventional fault propagation path estimating apparatus has a problem that, although it can estimate xe2x80x9ca fault propagation path in which a faulty state propagates from an input terminal and passes through a normal combinational logic circuitxe2x80x9d as shown in FIG. 8(a) which generates no logical contradiction during implication operations, or xe2x80x9ca fault propagation path which propagates from a fault existing within a combinational logic circuitxe2x80x9d as shown in FIG. 8(b) which generates a logical contradiction during processing, it cannot estimate xe2x80x9ca fault propagation path in which a fault exists within a combinational logic circuit and a faulty state propagates from an input terminalxe2x80x9d as shown in FIG. 8(c) or (d). Furthermore, the conventional fault propagation path estimating apparatus has limited applications since it cannot estimate a fault propagation path in a combinational logic circuit with multiple faults which result in a plurality of logical contradictions.
In addition, the conventional fault propagation path estimating apparatus has a problem that it cannot reproduce a fault propagation path within a combinational logic circuit at an arbitrary point during processing since it stores no history of the implication operations.
As another example of the fault propagation path estimating apparatus, a fault dictionary method is known in which a fault point is estimated by comparing a fault dictionary created from a previously performed fault simulation with a test result. However, since the fault simulation requiring a long calculation time must be performed for creating the fault dictionary, and the size of the dictionary is increased as the scale of the circuit is increased, the method is usually used only for detecting a single fault.
In JP-A-1-244384, described is an apparatus for determining a fault point by tracing a fault propagation path from an output terminal while the logical states of wires are respectively measured with physical analysis means such as an EB tester. However, since recent LSIs have increasingly finer chips and more highly layered wires, it is difficult to measure the logical state within the circuit with such physical analysis means.
In addition, there exists a method in which a predetermined test pattern is inputted to a combinational logic circuit to estimate a fault path based on the output result therefrom. However, since the method assumes that a fault occurs inside the combinational logic circuit and needs to create a test pattern which allows the detection of the fault at the output terminal, the creation of the test pattern requires an extremely long calculation time. Also, with such a method, it is difficult to extract only a fault propagation path relating to an output terminal (fault terminal) with its logical state recognized as being affected by the fault, and an output data amount is significantly increased if an attempt is made to determine the fault propagation path.
The present invention is made for solving the problems exhibited by the prior art as described above, and it is an object thereof to provide a fault propagation path estimating apparatus capable of accurately estimating a fault point even when a loop exists in a combinational logic circuit.
Also, it is another object of the present invention to provide a fault propagation path estimating method and a fault propagation path estimating apparatus capable of estimating a fault propagation path even when a fault exists inside a combinational logic circuit and a faulty state propagates from an input terminal, and capable of reproducing a fault propagation path during an implication operation.
To achieve the aforementioned objects, the fault propagation path estimating method according to the present invention is a method of estimating a fault propagation path for extracting a fault propagation path in a combinational logic circuit by repeating decisions and implication operations for a logical state to estimate a logical state inside the combinational logic circuit and comparing the estimated logical state with an expected value which indicates a logical state in a normal operation of the combinational logic circuit, the method comprising the steps of: detecting with the implication operation, as a newly implication-capable gate, a gate connected to an input side of a normal signal line estimated as in a logical state equal to the expected value and a gate connected to input and output sides of a signal line in a fault state estimated as in a logical state different from the expected value; and initializing a signal line on an output side of a gate estimated as in a logical state equal to the expected value with an implication operation for the implication-capable gate to a logical state before the implication operation.
Additionally, the present invention provides a method of estimating a fault propagation path for extracting a fault propagation path in a combinational logic circuit by repeating decisions and implication operations for a logical state to estimate a logical state inside the combinational logic circuit and comparing the estimated logical state with an expected value which indicates a logical state in a normal operation of the combinational logic circuit, the method comprising the step of: when a logical contradiction occurs between a logical state newly estimated with the implication operation and a logical state previously estimated, registering a signal line in which the logical contradiction occurs and recording the number of occurrences of the logical contradiction.
The result of the implication operation may be stored as history information, and when the number of occurrences of the logical contradiction exceeds a preset allowable number, the history information may be traced to initialize a logical state of a signal line causing a logical contradiction exceeding the allowable number to a state before an implication operation until the number of occurrences falls within the allowable number. The history information may be stored in a tree structure or in a stack structure.
On the other hand, the fault propagation path estimating apparatus according to the present invention is a fault propagation path estimating apparatus for extracting a fault propagation path in a combinational logic circuit by repeating decisions and implication operations for a logical state to estimate a logical state inside the combinational logic circuit and comparing the estimated logical state with an expected value which indicates a logical state in a normal operation of the combinational logic circuit, the apparatus comprising: an implication-capable normal signal line search subsection for detecting, as a newly implication-capable gate, a gate connected to an input side of a normal signal line estimated as in a logical state equal to the expected value with the implication operation; an implication-capable fault signal line search subsection for detecting, as a newly implication-capable gate, a gate connected to input and output sides of a signal line in a fault state estimated as in a logical state different from the expected value with the implication operation; and a normal output line logical state initializing subsection for initializing a signal line on an output side of a gate estimated as in a logical state equal to the expected value with an implication operation for the implication-capable gate to a logical state before the implication operation.
Additionally, the present invention provides a fault propagation estimating apparatus for extracting a fault propagation path in a combinational logic circuit by repeating decisions and implication operations for a logical state to estimate a logical state inside the combinational logic circuit and comparing the estimated logical state with an expected value which indicates a logical state in a normal operation of the combinational logic circuit, the apparatus comprising: a logical contradiction storing section for recording a signal line in which a logical contradiction occurs between a logical state newly estimated with the implication operation and a logical state previously estimated, and the number of occurrences of the logical contradiction; and a logical contradiction registering subsection for registering, when a logical contradiction occurs between a logical state newly estimated with the implication operation and a logical state previously estimated, a signal line in which the logical contradiction occurs and recording the number of occurrences of the logical contradiction in the logical contradiction storing section.
The fault propagation path estimating apparatus may further comprise a logical state storing section for storing the result of the implication operation as history information, and a contradiction signal line initializing subsection for tracing the history information when the number of occurrences of the logical contradiction exceeds a preset allowable number to initialize a logical state of a signal line causing a logical contradiction exceeding the allowable number to a state before an implication operation until the number of occurrences falls within the allowable number. The logical state storing section may store the history information in a tree structure or in a stack structure.
In the fault propagation path estimating method and fault propagation path estimating apparatus as mentioned above, a gate connected to the input side of a normal signal line in a logical state estimated as equal to its expected value with an implication operation is detected as a newly implication-capable gate, a gate connected to the output side of the normal signal line is not set as the implication-capable gate, and a signal line connected to the output side of a gate in a logical state estimated as equal to its expected value with an implication operation for the implication-capable gate is initialized to the logical state before the implication operation, thereby preventing a normal logical state from propagating to the output side during estimation.
When a logical contradiction occurs between the newly estimated logical state with the implication operation and the previously estimated logical state, the signal line with the generated logical contradiction is registered and the number of occurrences of logical contradictions is recorded. Thus, the implication operation can be continued even when the logical contradiction occurs.
Additionally, the result of the implication operation is stored as the history information. When the number of occurrences of logical contradictions exceeds the preset allowable number, the history information is traced to initialize the logical state of the signal line which causes the logical contradiction exceeding the allowable number to the state before the implication operation until the number of occurrences of logical contradictions falls within the allowable number, thereby making it possible to reproduce a fault propagation path in which the number of occurrences of logical contradictions falls within the allowable number.